package com.aw.puzzle.dropboxdiet;

import java.util.Arrays;

/**
 * User: gmc
 * Date: 29/01/11
 */
public class CombinationsGenerator {

    public int[] getNextCombination(int numberOfElements, int... currentCombination) {
        int[] nextCombination = null;
        int currentCombSize = currentCombination.length;
        int lastElementIdx = currentCombSize - 1;
        int lastElement = currentCombination[lastElementIdx];
        int maxIndex = numberOfElements - 1;
        boolean onlyIncrementTheLastElement = lastElement != maxIndex;
        if (onlyIncrementTheLastElement) {
            nextCombination = Arrays.copyOf(currentCombination, currentCombSize);
            nextCombination[lastElementIdx]++;
        } else {
            int firstElement = currentCombination[0];
            boolean isCombinationOfOneElement = currentCombSize == 1;
            boolean sizeMustBeChanged = isCombinationOfOneElement ||
                    (firstElement == numberOfElements - currentCombSize);
            if (sizeMustBeChanged) {
                int newSize = currentCombSize + 1;
                if (newSize <= numberOfElements) {
                    nextCombination = getFirstCombinationOfSize(newSize);
                }
            } else {
                int index = getIndexOfTheElementToBeIncremented(maxIndex, currentCombSize, currentCombination);
                nextCombination = Arrays.copyOf(currentCombination, currentCombSize);
                nextCombination[index]++;
                for (int i = index + 1; i < currentCombSize; i++) {
                    nextCombination[i] = nextCombination[i - 1] + 1;
                }
            }
        }
        return nextCombination;
    }

    public int[] getFirstCombinationOfSize(int size) {
        int[] firstCombination = new int[size];
        for (int i = 0; i < size; i++) {
            firstCombination[i] = i;
        }
        return firstCombination;
    }


    private int getIndexOfTheElementToBeIncremented(int maxIndex, int currentCombSize, int[] currentCombination) {
        for (int i = currentCombSize - 2; i >= 0; i--) {
            if (currentCombination[i] < maxIndex - 1) {
                int cantToAdd = currentCombSize - i;
                if (currentCombination[i] + cantToAdd <= maxIndex) {
                    return i;
                }
            }
        }
        return 0;
    }

}
